package com.wyx.suanfa;

/**
 * @author 王艺锡
 * @version 1.0
 */
public class exist {
    public static void main(String[] args) {
        //给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
        //
        //单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    }
}
/*
* class Solution {
    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];
        boolean flag;
        for(int i = 0;i<row;i++){
            for(int j = 0;j<col;j++){
                flag = check(board,visited,i,j,word,0);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        //如果当前字符不等于字符串中字符
        if(board[i][j] != s.charAt(k)){
            return false;
        }else if(k == s.length() - 1){//如果当前字符等于字符串中字符并且是最后一位
            return true;
        }
        visited[i][j] = true;
        //四个方向
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        //遍历四个方向
        for(int[] direction : directions){
            int newi = i + direction[0];
            int newj = j + direction[1];
            //如果没有越界
            if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length){
                //如果没有被重复访问
                if(!visited[newi][newj]){
                    result = check(board,visited,newi,newj,s,k + 1);
                    if(result){
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;

    }
}*/